package com.leetcode;

import java.util.PriorityQueue;

/**
 * 合并K个升序链表
 * 给你一个链表数组，每个链表都已经按升序排列。
 *
 * 请你将所有链表合并到一个升序链表中，返回合并后的链表。
 *
 * @author winson
 * @create 2022-03-30 11:49
 */
public class MergeKListsSolution {

    /**
     * 链表已经有序，可以利用本身有序的特性，通过对比所有链表中的第一个元素大小，获取到最小值，知道最小值属于那个链表，取其下一个进行比较
     * @param lists
     * @return
     */
    public ListNode mergeKLists(ListNode[] lists) {
        ListNode listNode = new ListNode();
        ListNode tail = listNode;
        PriorityQueue<MyListNode> priorityQueue = new PriorityQueue<>();
        for (ListNode listNode1 : lists) {
            if (listNode1 != null) {
                priorityQueue.add(new MyListNode(listNode1));
            }
        }
        while (!priorityQueue.isEmpty()) {
            // 取当前最小值
            MyListNode myListNode = priorityQueue.poll();
            tail.next = myListNode.listNode;
            tail = tail.next;
            if (myListNode.listNode.next != null) {
                priorityQueue.add(new MyListNode(myListNode.listNode.next));
            }
        }
        return listNode.next;
    }

    class MyListNode implements Comparable<MyListNode> {

        ListNode listNode;

        public MyListNode(ListNode listNode) {
            this.listNode = listNode;
        }

        @Override
        public int compareTo(MyListNode o) {
            return listNode.val - o.listNode.val;
        }
    }

}
